package com.wtgroup.demo.面试题.我的面试.华为OD笔试230627;

import java.util.HashMap;
import java.util.Stack;

/**
 * 检查括号匹配
 * @author nisus
 * @version 0.1
 * @since 2023/7/8 15:34
 */
public class Q4_一面_有效括号 {
    /*
    检查括号匹配
    给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
    有效字符串需满足：
    左括号必须用相同类型的右括号闭合。
    左括号必须以正确的顺序闭合。
    示例 1：
    输入：s = "()"
    输出：true
    示例 2：
    输入：s = "()[]{}"
    输出：true
    示例 3：
    输入：s = "(]"
    输出：false
    示例 4：
    输入：s = "([)]"
    输出：false
    示例 5：
    输入：s = "({[]})"
    输出：true
    提示：
    1 <= s.length <= 10^4
    s 仅由括号 '()[]{}' 组成
    */
    public static void main(String[] args) {

        HashMap<String, String> map = new HashMap<String, String>();
        map.put(")", "(");
        map.put("]", "[");
        map.put("}", "{");

        String str = "({[]})";
        boolean res = func(str, map);
        System.out.println(res);
    }

    static boolean func(String str, HashMap<String, String> map) {
        Stack<String> stack = new Stack<String>();
        String[] split = str.split("");
        for (String s : split) {
            if (!map.containsKey(s)) {
                stack.push(s);
            } else {
                if (stack.isEmpty()) {
                    return false;
                }
                String pop = stack.pop();
                if (!map.get(s).equals(pop)) {
                    return false;
                }
            }
        }

        return true;
    }


}
